package com.atguigu.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author durant
 * @create 2021-11-15 14:49
 */
public class QuickSort {
    public static void main(String[] args) {
//        int[] arr = {-9,78,0,23,-567,70,-1};
//        int[] arr = {7,2,4,6,6,6,6,6,8};
//        quickSort(arr,0,arr.length-1);
//        System.out.println(Arrays.toString(arr));
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
          arr[i] = (int) (Math.random() * 8000000);
        }

        Date date1 = new Date(System.currentTimeMillis());
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("hh:mm:ss.SSS");
        String format = simpleDateFormat.format(date1);
        quickSort(arr,0,arr.length-1);
        Date date2 = new Date(System.currentTimeMillis());
        String forma2 = simpleDateFormat.format(date2);
        System.out.println("排序前的时间：" + format);
        System.out.println("排序后的时间：" + forma2);
    }
    public static void quickSort(int[] arr,int left,int right){
        int l = left; // 左下标 即0
        int r = right; // 右下标 即arr.length()
        // pivot中轴值
        int pivot = arr[(l + r)/2]; // 中轴的意思
        int temp = 0;// 临时变量，交换时使用
        // while循环的目的是让比pivot值小的值放到左边，比pivot值大的值放到右边
        while (l < r){
            while (arr[l] < pivot){// 在左边一直找，找到大于等于pivot的值才退出
                l++;
            }
            while (arr[r] > pivot){// 在右边一直找，找到小于等于pivot的值才退出
                r--;
            }
            if (l >= r){// 这样的话表示左边都是小于等于pivot的值，右边都是大于等于pivot的值
                break;
            }
            // 交换
            temp = arr[r];
            arr[r] = arr[l];
            arr[l] = temp;
            /*
            这里为什么做这个操作是因为当数组为{-1.20,-2,0,1,2,3}时，pivot等于0 ，但是第一次进行运算时，l再20的位置，r因为右边没有比0小的，所以会一直减少
            最后指向pivot的坐标，进行变换，变为-1，0,-2,20,1,2,3，此时arr[l] == pivot ==0 ，因此只需要将r的左边进行变换即可（即r--）
            * */
            // 当第一个while中arr[l]==pivot后，第二个while中的r++了，但是现在不进行比较，
            // 如果交换完后，发现这个arr[l]==pivot 相等,r--前移
            if (arr[l] == pivot){
                r -= 1;
            }
            // 如果交换完后，发现这个arr[r]==pivot 相等,l--前移
            if (arr[r] == pivot){
                l += 1;
            }
        }
        // 如果l == r,必须l++ ,r-- 否则会出现栈溢出
        if (l == r){//当不断进行递归时，如果不限制l r的值，就会导致不断地无穷递归，因为就算需要递归的数只有一个时，left始终小于l，right始终小于r
            //所以就需要将l 和r进行变化，在下面的递归条件中进行限制
            l++;
            r--;
        }
        // 向左递归
        if (left < r){
            quickSort(arr, left,r);
        }
        // 向右递归
        if (right > l){
            quickSort(arr, l, right);
        }
    }
}
